package week_02;

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis_22 {
    private ArrayList[] cache = new ArrayList[10];

    // 加缓存 每个n有对应 的结果集
    public List<String> generateParenthesis(int n) {
        //输入：n = 3
        //输出：["((()))","(()())","(())()","()(())","()()()"]
        // 边界 当n=0
        System.out.println(n);
        if (cache[n] != null) return cache[n];
        if (n == 0) {
            return new ArrayList<String>() {{
                add("");

            }};
        }
        ;
        // 分（a）b拆解问题为：k对 ，1对固定，n-k对括号的子问题
        ArrayList<String> ans = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            List<String> k_ans = generateParenthesis(i - 1);
            List<String> k_1_ans = generateParenthesis(n - i);
            // 将子结果拼接
            for (String s1 : k_ans) {
                for (String s2 : k_1_ans) {
                    System.out.println("(" + s1 + ")" + s2);
                    ans.add("(" + s1 + ")" + s2);
                }
            }
        }
        cache[n] = ans;
        return ans;
    }

    // 没有缓存
    public List<String> generateParenthesis2(int n) {
        //输入：n = 3
        //输出：["((()))","(()())","(())()","()(())","()()()"]
        // 边界 当n=0
        System.out.println(n);
        if (n == 0) {
            return new ArrayList<String>() {{
                add("");

            }};
        }
        ;
        // 分（a）b拆解问题为：k对 ，1对固定，n-k对括号的子问题
        List<String> ans = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            List<String> k_ans = generateParenthesis(i - 1);
            List<String> k_1_ans = generateParenthesis(n - i);
            // 将子结果拼接
            for (String s1 : k_ans) {
                for (String s2 : k_1_ans) {
                    System.out.println("(" + s1 + ")" + s2);
                    ans.add("(" + s1 + ")" + s2);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        GenerateParenthesis_22 test = new GenerateParenthesis_22();
        List<String> ans = test.generateParenthesis(2);
        for (String s : ans) {
            System.out.println(s);
        }

    }
}
